'''
email: chenyan@feling.net

倒位序
'''
import math

def partition(l, begin, end):
    l0 = []
    l1 = []
    median = (begin+end) // 2
    for i in range(begin, end):
        if i%2 == 0:
            l0.append(l[i])
        else:
            l1.append(l[i])
    l[begin:end] = []
    l[begin:begin] = l0 + l1
    return median

def bit_reversed_order(l, begin=0, end=-9):
    '''
    >>> l = [0, 1, 2, 3, 4, 5, 6, 7]
    >>> bit_reversed_order(l) 
    >>> l
    [0, 4, 2, 6, 1, 5, 3, 7]
    
    >>> l1 = [0, 1, 2, 3, 4, 5, 6]
    >>> bit_reversed_order(l1) 
    -1
    '''

    if end == -9:
        end = len(l)

    N = end - begin
    if math.log2(N)%1 != 0:
        return -1
    if end-begin >= 4:
        median = partition(l, begin, end)
        bit_reversed_order(l, begin, median)
        bit_reversed_order(l, median, end)

def x_bit_reversed_order(l):
    '''
    >>> l = [0, 1, 2, 3, 4, 5, 6, 7]
    >>> result = []
    >>> for i in x_bit_reversed_order(l):
    ...    result.append(i)
    >>> result
    [0, 4, 2, 6, 1, 5, 3, 7]
    '''
    N = len(l)
    for i in range(N):
        l_index = list(bin(i)[2:])
        l_index.reverse()
        for j in range(len(l_index),int(math.log2(N))):
            l_index.append('0')
        yield l[int(''.join(l_index), 2)]

if __name__=='__main__':
    import doctest
    doctest.testmod()
